package Algorithm.DynamicPlanning;

public class Code08_MinBoat {
    public static int minBoat(int[] arr, int limit){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int lessR = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] <= limit / 2){
                lessR = i;
                break;
            }
        }
        if (lessR == -1){
            return arr.length;
        }
        int L = lessR;
        int R = lessR + 1;
        int lessUnused = 0; // 画X的数量统计
        while (L >= 0){
            int solved = 0; // 此时的L，让R画过了多少数
            while (R < arr.length && arr[L] + arr[R] <= limit){
                solved++;
                R++;
            }
            if (solved == 0){
                lessUnused++;
                L--;
            } else {
                L = Math.max(-1, L - solved);
            }
        }
        int lessAll = lessR + 1; // 左半区总数
        int lessUsed = lessAll - lessUnused; // 左半区画对号的数量
        // 右半区没配对的数量
        int moreUnused = (arr.length - lessR - 1 - lessUsed > 0 ? arr.length - lessR - 1 - lessUsed : 0);
        return lessUsed + ((lessUnused + 1) >> 1) + moreUnused;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5 };
        int weight = 6;
        System.out.println(minBoat(arr, weight));
    }
}
